'''
Created on Aug 23, 2011

@author: nktran
'''
import re

class FSA:
    """
    Simple implementation of finite state automata
    Currently, DFSA are implemented that means there is only
    one states can reach from state q with a string s
    """
      
    def __init__(self):
        """
        @var states: store all states of the automata
        @var final_states: store all final state
        @var start state: store the start state
        @var trans: store transitions (q_i, a) = q_j
        @var accept_letters: contains all letters that can be used
        to reach to final state from a state q     
        """
        self.states = set()
        self.final_states = set()
        self.start_state = ""
        self.trans = dict()
        self.__parent = dict()
        self.accept_letters = dict()
        
    def init(self, ext = ""):
        """
        Initialize fsa from a file fsa.[ext]. It is used to 
        test the fsa with examples.
        """
        fin = open("fsa."+ ext, "r")
        flag = 0
        try:
            for line in fin.read().split("\n"):                                
                if line.find("#States") != -1: flag = 1; continue
                if line.find("#Start") != -1: flag = 2; continue
                if line.find("#Final") != -1: flag = 3; continue
                if line.find("#Transitions") != -1: flag = 4; continue
                if line.find("#Accepted Letters") != -1: break
                if len(line.strip()) < 1: continue                
                temp = re.split("\s+", line.strip())
                if flag == 1:
                    for e in temp:
                        self.states.add(e)
                elif flag == 2:
                    self.start_state = temp[0]
                elif flag == 3:
                    for e in temp:
                        self.final_states.add(e)
                elif flag == 4:
                    self.trans[(temp[0], temp[1])] = temp[2]
        finally:
            fin.close()
    
    def construct(self, alg):
        """
        Construct fsa from the table learned by angluin algorithm
        
        states := {row(s) for each s in prefix set of the table
        start_state := {row(_lamda_)}
        final_states := {row(s) such that s belongs to prefix set and
        the value of the cell _lamda_ in row(s) is 1}
        trans := {trans(row(s), a) = row(s.a)}
        
        @param alg: table returned from alg 
        """
        # keep track to find value of node
        temp = list()
        temp_val = dict()
        node_val = dict()
         
        for s in alg.prefix:
            if alg.table[s] not in temp:
                newnode = 'q' + str(len(self.states))
                self.states.add(newnode)
                
                node_val[newnode] = s
                temp_val[len(temp)] = newnode                
                temp.append(alg.table[s])
                 
                if alg.table[s][""] == 1:
                    self.final_states.add(newnode)
                    
        self.start_state = 'q0'
        for q in self.states:
            for a in alg.alphabet:
                next_state = temp_val[temp.index(alg.table[node_val[q]+a])]
                self.trans[(q,a)] = next_state
                if next_state in self.__parent.keys():
                    self.__parent[next_state].append((q,a))
                else:
                    self.__parent[next_state] = [(q,a)]
        
        # Saving data to file
        self.compute_accepted_letters()
        self.toFile(alg.__ext__)
        
    def compute_accepted_letters(self):
        """
        Compute all accepted letters from each state
        
        The process is calculated from final states until the start state
        is reached.
        """
        if len(self.final_states) == 0:
            return
        temp = self.final_states
        visited_state = set()
        while True:
            new_temp = set()
            for state in temp:
                for p_state, letter in self.__parent[state]:
                    if p_state not in visited_state:
                        new_temp.add(p_state)                                                
                        if p_state not in self.accept_letters.keys():
                            self.accept_letters[p_state] = [letter]
                        else:
                            self.accept_letters[p_state].append(letter)                    
            temp = new_temp
            for state in new_temp:
                if state not in visited_state:
                    visited_state.add(state)
                    
            if self.start_state in visited_state:
                break

    def parse(self, inst):
        """
        Check if the instance can be accepted by the FSA
        Because currently FSA is deterministic, thus it is simply implemented
        
        @param inst: instance need to be checked 
        @return: True/False
        """
        q = self.start_state
        for tok in re.split('\s+', inst):
            if not self.trans.has_key((q,tok)):
                return False
            q = self.trans[(q, tok)]
        
        if q not in self.final_states:
            return False
        return True        
                
    def toString(self):
        """
        Display current FSA to screen
        """
        print "States: ",
        for q in self.states:
            print q,
        print
        print "Start state: ", self.start_state
        print "Final state: ", 
        for fq in self.final_states:
            print fq,
        print
        print "Transitions: "
        keys = self.trans.keys()
        keys.sort()        
        for k in keys:
            print k[0], '  ', k[1], '    ----->   ', self.trans[k]
        print                  
    
    def toFile(self, ext = ""):
        """
        Store FSA into file for next usages.
        
        @param ext: file extension 
        """
        fout = open('fsa.' + ext, 'w')
        try:
            fout.write('#States:' + '\n')
            for q in self.states:
                fout.write(q + " ")
            fout.write('\n' + "#Start:" + '\n')
            fout.write(self.start_state + '\n')
            fout.write("#Final:" + "\n")
            for fq in self.final_states:
                fout.write(fq + " ")
            fout.write("\n" + "#Transitions:" + "\n")
            trans_keys = self.trans.keys()
            trans_keys.sort()        
            for k in trans_keys:
                fout.write(k[0] + " " + k[1] + " " + self.trans[k] + "\n")
            fout.write("\n" + "#Accepted Letters" + "\n")
            acc_keys = self.accept_letters.keys()
            acc_keys.sort()
            for k in acc_keys:
                fout.write(k + ': ')
                for val in self.accept_letters[k]:
                    fout.write(val + ', ')
                fout.write('\n') 
            
        finally:
            fout.close()                  
        